In recent years, the importance of network security has been widely recognized. For ensuring security, a variety of services on networks are configured to be provided to only specified individuals. For this reason, these services entail personal authentication for a service user before the user can utilize a service. However, a plurality of historical data collected in the course of authentication reveal private information as to when, where, and what the same service user has done, resulting in a violation of the individual's privacy. Accordingly, from the viewpoint of privacy, it can be said that the personal authentication should be desirably done as least frequently as possible.
As a measure for increasing the anonymity of a user who is to be authenticated, a method may be contemplated in which the same ID and password is issued to all members of a service. Since this method authenticates all members using the same ID and password, the authentication can be done without identifying individuals. However, if any of the members betrays the password to a person other than the members, a new password must be issued and transmitted to all the members in order to provide the service to only the members. In addition, even if the behavior of a user who is to be authenticated includes an operation which may break an agreement and the like so that the user who is to be authenticated will be identified, the manager cannot identify the user who is to be authenticated.
Patent Document 1 describes an anonymous authentication scheme. This anonymous authentication scheme is an authentication scheme which allows a manager to identify and/or exclude a user who is to be authenticated as necessary, while maintaining the anonymity of the user who is to be authenticated. This anonymous authentication system further allows anyone to determine whether the authentications that are carried out a plurality of times are actions performed by the same user who is to be authenticated or by different users who are to be authenticated. This has the advantage that in a for-profit members-only service and the like, the manager can acquire information on repeatedly access members, but is problematic in that if a particular user who is to be authenticated is identified for some reason, a past authentication history of the user who is to be authenticated is revealed in its entirety. Moreover, the anonymous authentication scheme of Patent Document 1 suffers from a problem in which since the manager knows the IDs and passwords of all members, the manger can act while disguised as a member.
Further, Non-Patent Document 1 describes an anonymous authentication scheme which employs a group signature. According to these anonymous authentication schemes, it is impossible to determine whether authentications that are carried out a plurality of times are actions performed by the same user who is to be authenticated or by different users who are to be authenticated, and a manager is prevented from taking action disguised as another member. However, these schemes present a problem in which a large calculation cost is involved for generating data (hereinafter referred to as “authentication data”) that is necessary for authenticating a user who is to be authenticated.    Patent Document 1: JP2006-235661A    Non-Patent Document 1: J. Camenisch and J. Groth. Group signatures: better efficiency and new theoretical aspects. Forth Int. Conf. on Security in Communication Networks—SCN 2004, LNCS 3352, Springer, 2005.